/*  Copyright 2010 Daniel Brasil Magnani
 *  Created on: Dec 20, 2010
 *      Author: daniel
 */

#include "constructive.h"
#include <algorithm>
using std::vector;

void Constructive::CounterVector(std::vector<int> *cost_counter) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance().get_constraint_list();

  for (int j = 0; j < constraint_size_; j++) {
    (*cost_counter)[j] = 0;
    for (int k = 0; k < constraint_list[j].p-1; k++) {
      if ( solution_[solution_size_-k-1].constraints[j] == 1 )
        (*cost_counter)[j]++;
    }
  }
}

void Constructive::UtilizationRate(std::vector<Car> *S) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance().get_constraint_list();

  for (int i = 0; i < constraint_size_; i++ )
    utilization_rate_[i] = 0;
  for (int i = 0; i < (*S).size(); i++) {
    for (int j = 0; j < constraint_size_; j++)
      if ( (*S)[i].constraints[j] == 1)
        utilization_rate_[j]++;
  }

  for ( int i = 0; i < constraint_size_ ; i++ )
    utilization_rate_[i] = (static_cast<float>(utilization_rate_[i])/
                            static_cast<float>((*S).size()))/
                           (static_cast<float>(constraint_list[i].n)/
                            static_cast<float>(constraint_list[i].p));

  for (int i = 0; i < (*S).size(); i++) {
    (*S)[i].utilization_rate = 0;
    for ( int j = 0; j < constraint_size_; j++ ) {
      if ( (*S)[i].constraints[j] == 1)
        (*S)[i].utilization_rate += utilization_rate_[j];
    }
  }
}

int Constructive::CostFrontInsert(
    const std::vector<int> &cost_counter,
    const Car temp_car) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance().get_constraint_list();

  int cost = 0;
  for (int j = 0; j < constraint_size_; j++) {
    if ( cost_counter[j] >= constraint_list[j].n ) {
      if (temp_car.constraints[j] == 1)
        cost += ((cost_counter[j] - constraint_list[j].n) + 1);
      else
        cost += (cost_counter[j] - constraint_list[j].n);
    }
  }

  return cost;
}

Constructive::Constructive() {
  vector<Constraint> constraint_list;
  vector<Car> yesterday_cars;
  vector<Car> today_cars;
  constraint_list = Instance::get_instance().get_constraint_list();
  yesterday_cars = Instance::get_instance().get_yesterday_cars();
  today_cars = Instance::get_instance().get_today_cars();

  solution_.reserve(today_cars.size()+yesterday_cars.size());
  utilization_rate_.reserve(constraint_list.size());
  constraint_size_ = constraint_list.size();
  solution_size_ = solution_.size();
  yesterday_size_ = yesterday_cars.size();

//  printf("Yesterday size: %d\nToday size: %d\nConstraint size: %d\n", yesterday_size_, today_cars.size(), constraint_size_);
}

std::vector<Car> Constructive::get_solution() {
  return solution_;
}

int Constructive::Execute() {
  vector<Constraint> constraint_list;
  vector<Car> yesterday_cars;
  vector<Car> today_cars;
  constraint_list = Instance::get_instance().get_constraint_list();
  yesterday_cars = Instance::get_instance().get_yesterday_cars();
  today_cars = Instance::get_instance().get_today_cars();

  vector<Car> S;
  vector<Car>::iterator car_iterator;
  vector<int> cost_counter;
  vector<int> cars_violations;
  vector<int> LRC;
  int violations_min;
  int violations = 0;
  int v;

  S.reserve(today_cars.size());
  LRC.reserve(today_cars.size());
  cars_violations.reserve(today_cars.size());
  cost_counter.reserve(constraint_size_);
  copy(yesterday_cars.begin(), yesterday_cars.end(), back_inserter(solution_));
  copy(today_cars.begin(), today_cars.end(), back_inserter(S));
  solution_size_ = solution_.size();

  while ( S.size() != 0 ) {
    violations_min = INT_MAX;
    CounterVector(&cost_counter);
    LRC.clear();
    UtilizationRate(&S);

    for (int i = 0; i < S.size(); i++) {
      violations = CostFrontInsert(cost_counter, S[i]);
      cars_violations[i] = violations;
      if ( violations < violations_min ) {
        v = i;
        violations_min = violations;
      }
    }

    float max_utilization_rate = 0;
    for (int i = 0; i < S.size(); i++) {
      if ( cars_violations[i] == violations_min &&
           S[i].utilization_rate > max_utilization_rate ) {
          max_utilization_rate = S[i].utilization_rate;
      }
    }

    for (int i = 0; i < S.size(); i++) {
      if ( cars_violations[i] == violations_min &&
           S[i].utilization_rate == max_utilization_rate ) {
          LRC.push_back(i);
      }
    }

//    v = 0;
//    v = LRC[rand()%LRC.size()];
    v = rand()%S.size();    

    solution_.push_back(S[v]);
    car_iterator = S.begin();
    advance(car_iterator, v);
    S.erase(car_iterator);
    solution_size_ = solution_.size();
  }
  return true;
}
